Order and It's Guarantees
#orderingevents #events
Causality imposes an ordering of events and any system that obeys this order can be called #causaliyconsistent iyconsistent.
#Linearizability obeys a total order, which is, it respects the causality of events.
#Causality defines the partial order where some events can be ordered and others not.
#sequencenumberordering
keeping track of all causal dependencies its a big overhead. We can use #sequencenumber or #timestamps . Timestamps can come from logical clocks, which increment at each operation. For single-leader replications, the replication log can maintain the total order of events (writes) based on this sequence number. Thus, any follower that replicates it will be causally consistent.
#noncausalsequencenumbering
Non causal sequence numbering is used in leaderless/multileader replication/partitioned applications but there are some used metods in practice:
- number being generated by a range by node. ex: odd and even between two node.
- attaching timestamp, which might be sufficiente for total ordering of events.
- preallocation on a block of numbers
All these three methods are inconsistent with causality.
#lamporttimestamp #lamport #timestamps
- its key composed by the N operations processed by the node and the node ID.
If you have the same amount of operations, the one with the greater ID is the greater timestamp.
This idea by itself doesnt make it totally casually consistent; the key idea behing Lamport timestamps is:
"Every node and client keeps track of the maximum counter value it has seen so far, and includes that maximum on every request. When a node receiver a req o resp with a maximum greater than its own counter value, it immediatelly increases its own to this maximum"
Lamport Timestamps ARE NOT Version Vectors. They seem similar, but have different purposes: version vector can tell wether two operations are concurrent or whether one is causally dependent on the another operation.
Lamport Timestamps enforce TOTAL ORDERING.
Total Ordering of Events are not enought for ensuring uniqueness constraints. It its necessary to have #totalorderbroadcast #atomicbrodcast
Total Order Broadcast, informally, describe the protocol of
- Reliable Delivery: no messages are lost. if delivered, they are all delivered to all nodes.
- Totally Ordered Delivery: all nodes receive the message in the same order
Examples of services that implement Total Order Broadcast. ZooKeeper and etcd.
Thus, total order broadcast is exactly the necessary for database replication. if every replica processes the same write in an ordered fashion, each replica will main its consistency. Princple know as #statemachinereplication #statemachine
#fencingtokens Total order broadcast is useful for implemeting fencing tokens. Every req to acquire the lock is appended to the log, and sequentially numbered. The sequence itself can be uses as fencing token. ZooKeeper calls the sqeuence number zxid
#distributedtransactions